package c_heap_sort;
/**
 *索引堆的应用场景是：堆中元素是字符串等类型 大量的swap会比较消耗内存，都没有swap整数轻量； 还有就是数组的二元性，索引有意义时，我们可能会常有change(更新)操作。
 *比如索引代表进程编号，值代表优先级，那不可避免会需要change操作；
 *
 *改造也很简单。
 *巧妙的是，我们可以在构造堆的时候，不直接使用data，而是使用data的索引，它们是一一对应的；这样下来我们访问堆中数据就是访问堆化的indexes序列，而data现在就相当于不见光的数据库；
 *但是，我们的需求往往是面向data数组的。比如 我要修改进程号为66的优先级为X，现在我就只能先遍历indexes找到66索引，然后才能访问到data正确的位置进行change；然后进行合理sift让 堆(indexes) 自适应；
 *显然，change操作是O(n)级别的，再加上找到索引那次的sift操作(O(logn))，整体还是O(n)级别；这样的操作效率是比较低的，
 *
 *我们只要优化遍历找索引的这个操作即可。所以自然而然的是，再开辟一个类似indexes的数组。辅助我们实现：indexes数组的索引和data的索引一一对应起来 即可。这样就又实现了随机访问；
 *数组reverse。 比如：我们想访问进程号为77的进程，就直接访问reverse[77]，里面存的就是77索引号 在  indexes代表的堆  中的位置；
 *
 *具体如图所示，结合代码；   
 *
 *整体过程：    欲知道索引号为i的元素在堆中的位置，又不想遍历，就模拟一个映射，让reverse数组的索引和i在堆中位置的索引对应起来。。知目标即得索引；
 *reverse[i](模拟随机访问) —-定位> indexes[reverse[i]](然后维护堆) —-访问> data[i]（做比较）
 */
// 最大索引堆
public class IndexMaxHeap<Item extends Comparable> {

    protected Item[] data;      // 最大索引堆中的数据
    protected int[] indexes;    // 最大索引堆中的索引, indexes[x] = i 表示索引i在x的位置
    protected int[] reverse;    // 最大索引堆中的反向索引, reverse[i] = x 表示索引i在x的位置
    protected int count;
    protected int capacity;

    // 构造函数, 构造一个空堆, 可容纳capacity个元素
    public IndexMaxHeap(int capacity){
        data = (Item[])new Comparable[capacity+1];
        indexes = new int[capacity+1];
        reverse = new int[capacity+1];
        for( int i = 0 ; i <= capacity ; i ++ )
            reverse[i] = 0;

        count = 0;
        this.capacity = capacity;
    }

    // 返回索引堆中的元素个数
    public int size(){
        return count;
    }

    // 返回一个布尔值, 表示索引堆中是否为空
    public boolean isEmpty(){
        return count == 0;
    }

    // 向最大索引堆中插入一个新的元素, 新元素的索引为i, 元素为item
    // 传入的i对用户而言,是从0索引的
    public void insert(int i, Item item){

        assert count + 1 <= capacity;
        assert i + 1 >= 1 && i + 1 <= capacity;

        // 再插入一个新元素前,还需要保证索引i所在的位置是没有元素的。
        assert !contain(i);      						//assert boolean; 为true才继续执行，否则抛出断言不满足的异常；也就是后边的代码是based on that the assert is true;

        i += 1;
        data[i] = item;
        indexes[count+1] = i;
        reverse[i] = count + 1;
        count ++;

        shiftUp(count);
    }

    // 从最大索引堆中取出堆顶元素, 即索引堆中所存储的最大数据
    public Item extractMax(){
        assert count > 0;

        Item ret = data[indexes[1]];
        swapIndexes( 1 , count );
        reverse[indexes[count]] = 0;
        count --;
        shiftDown(1);

        return ret;
    }

    // 从最大索引堆中取出堆顶元素的索引
    public int extractMaxIndex(){
        assert count > 0;

        int ret = indexes[1] - 1;
        swapIndexes( 1 , count );
        reverse[indexes[count]] = 0;
        count --;
        shiftDown(1);

        return ret;
    }

    // 获取最大索引堆中的堆顶元素
    public Item getMax(){
        assert count > 0;
        return data[indexes[1]];
    }

    // 获取最大索引堆中的堆顶元素的索引
    public int getMaxIndex(){
        assert count > 0;
        return indexes[1]-1;
    }

    // 看索引i所在的位置是否存在元素
    boolean contain( int i ){
        assert  i + 1 >= 1 && i + 1 <= capacity;
        return reverse[i+1] != 0;
    }

    // 获取最大索引堆中索引为i的元素
    public Item getItem( int i ){
        assert contain(i);
        return data[i+1];
    }

    // 将最大索引堆中索引为i的元素修改为newItem
    public void change( int i , Item newItem ){

        assert contain(i);

        i += 1;
        data[i] = newItem;

        // 有了 reverse 之后,
        // 我们可以非常简单的通过reverse直接定位索引i在indexes中的位置
        shiftUp( reverse[i] );
        shiftDown( reverse[i] );
    }

    // 交换索引堆中的索引i和j
    // 由于有了反向索引reverse数组，
    // indexes数组发生改变以后， 相应的就需要维护reverse数组
    private void swapIndexes(int i, int j){
        int t = indexes[i];
        indexes[i] = indexes[j];
        indexes[j] = t;

        reverse[indexes[i]] = i;
        reverse[indexes[j]] = j;
    }

    //********************
    //* 最大索引堆核心辅助函数
    //********************

    // 索引堆中, 数据之间的比较根据data的大小进行比较, 但实际操作的是索引
    private void shiftUp(int k){

        while( k > 1 && data[indexes[k/2]].compareTo(data[indexes[k]]) < 0 ){
            swapIndexes(k, k/2);
            k /= 2;
        }
    }

    // 索引堆中, 数据之间的比较根据data的大小进行比较, 但实际操作的是索引
    private void shiftDown(int k){

        while( 2*k <= count ){
            int j = 2*k;
            if( j+1 <= count && data[indexes[j+1]].compareTo(data[indexes[j]]) > 0 )
                j ++;

            if( data[indexes[k]].compareTo(data[indexes[j]]) >= 0 )
                break;

            swapIndexes(k, j);
            k = j;
        }
    }

    // 测试 IndexMaxHeap
    public static void main(String[] args) {

        int N = 1000000;
        IndexMaxHeap<Integer> indexMaxHeap = new IndexMaxHeap<Integer>(N);
        for( int i = 0 ; i < N ; i ++ )
            indexMaxHeap.insert( i , (int)(Math.random()*N) );

    }
}